package bTree.LeetCode;

import java.util.HashSet;
import java.util.Set;

public class 最小覆盖子串 {
    public String minWindow(String s, String t) {
        int[] cntS = new int[128];
        int[] cntT = new int[128];
        String res = "";
        Set<Character> set = new HashSet<>();
        if (s.length() < t.length()) return "";
        for (int i = 0; i < t.length(); i++) {
            cntT[t.charAt(i)]++;
            set.add(t.charAt(i));
        }
        for (int i = 0; i < t.length() - 1; i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                cntS[c]++;
            }
        }
        int left = 0;
        for (int right = t.length() - 1; right < s.length(); right++) {
            char c = s.charAt(right);
            if (set.contains(c)) {
                cntS[c]++;
            }
            while (check(cntT, cntS)) {
                if (res.isEmpty()) {
                    res = s.substring(left, right + 1);
                } else {
                    res = s.substring(left, right + 1).length() < res.length() ? s.substring(left, right + 1) : res;
                }
                if (set.contains(s.charAt(left))) {
                    cntS[s.charAt(left)]--;
                }
                left++;
            }
        }
        return res;
    }

    private boolean check(int[] cntT, int[] cntS) {
        for (int i = 0; i < 128; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        return true;
    }
}
